﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

//class A
//{
//public:
//	static int _a;//普通的静态成员必须在类外进行初始化
//	const static int _b = 10;//const修饰的静态成员可以在类内进行初始化
//};
//int A::_a = 10;

//#pragma pack(8)
//class B
//{
//};


//int fun(int a) { return 1; }
////void fun(int a) {}//函数类型不同不能构成重载
//
//int fun(int a, int b) { return 1; }
//int fun(int c, char a){ return 1; }
//int fun(char c, int a) { return 1; }


//int main()
//{
//	//A a;
//	//a._a = 10;
//
//	////静态成员可以直接通过类名进行调用 -- 取决于权限
//	//cout << A::_a << endl;
//
//	//空类的大小为1 -- X64和X32一样，并且于对齐数无关
//	/*B b;
//	cout << sizeof(b) << endl;*/
//
//
//	//涉及到常量折叠 --。。
//	const int a = 10;
//	int* p = (int*)(&a);
//
//	*p = 20;
//	cout << a << " " << *p << endl;
//	return 0;
//}

//经典面试题
//class A
//{
//public:
//    virtual void func(int val = 1) { std::cout << "A->" << val << std::endl; }
//    virtual void test() { func();}
//};
//
//class B : public A
//{
//public:
//    void func(int val = 0) { std::cout << "B->" << val << std::endl; }
//};
//
//int main(int argc, char* argv[])
//{
//    A* p = new B;
//    p->test();
//    return 0;
//}

//求二进制最大连续1的个数
//int main()
//{
//    int n;
//    cin >> n;
//
//    int max = 0;
//    int cnt = 0;
//    for (int i = 0; i < 32; ++i)
//    {
//        if (n & 1)
//        {
//            cnt++;
//        }
//        else
//        {
//            if (cnt > max)
//                max = cnt;
//            cnt = 0;
//        }
//        n = n >> 1;
//    }
//    cout << max;
//    return 0;
//}

//找公共祖先
class LCA {
public:
    int getLCA(int a, int b) {
        //思路：满二叉树的子节点与父节点之间的关系为root = child / 2
        //利用这个关系，如果a ！= b，就让其中的较大数除以2， 如此循环知道a == b，
        //即是原来两个数的最近公共祖先
        while (a != b)
        {
            if (a > b)
                a /= 2;
            else
                b /= 2;
        }
        return a;
    }
};

//int main()
//{
//    LCA a;
//    int ret = a.getLCA(3, 7);
//    cout << ret << endl;
//    return 0;
//}

//class A
//{
//public:
//    ~A();
//};
//
//A::~A()
//{
//    delete this;
//    this = nullptr;
//}
//int main()
//{
//    A a;
//    a.~A();
//    return 0;
//}


//#include <iostream>
//#include <cmath>
//using namespace std;
//
//bool fun(int a)
//{
//    for (int i = 2; i < a-1; ++i)
//    {
//        if (a % i == 0)
//            return false;
//    }
//    return true;
//}
//int main()
//{
//    int a1 = 0, a2 = 100000;//素数对
//    int x = a2 - a1;
//    int n;
//    cin >> n;
//
//    int i = 1;
//    while (1)
//    {
//        a1 = i++;
//        a2 = n - a1;
//
//        if (!fun(a1) || !fun(a2))
//        {
//            continue;
//        }
//        if (a2 - a1 < 0)
//            break;
//        if (a2 - a1 < x)
//        {
//            x = a2 - a1;
//        }
//    }
//    cout << a1 << endl;
//    cout << a2 << endl;
//    return 0;
//}

//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//
//    int flag = 0;
//    for (int i = 2; i < sqrt(n); ++i)
//    {
//        if ((n % i) == 0)
//        {
//            flag = 1;
//            break;
//        }
//    }
//    if (flag)
//        cout << "false" << endl;
//    else
//        cout << "true" << endl;
//    return 0;
//}

//在继承时析构函数建议写成虚函数的重写
class Person
{
public:
	virtual ~Person() {
		cout << "~Person" << endl;
	}
	int _a;
};
class Student : public Person
{
public:
	//override检查该虚函数是否重写   final修饰的类不能被继承下去
	virtual ~Student() {
		cout << "~Student" << endl;
	}
	int _b;
};

//int main()
//{
//	//普通的场景下是没有问题的
//	//Person p;
//	Student s;
//
//	//如果不是重写成虚函数的话就会出错 -- 两次person 没有子类的析构student
//	//因为delete的时候看的是类型，如果没有写成虚函数，那么p2就会直接去调用父类的析构函数，子类的就不会调用
//	//如果写成了虚函数的话，p2就会到虚表中去调用student类型的析构函数，子类的析构函数调用玩之后，会自动
//	//的调用父类的析构函数，这就完成了。
//	Person* p1 = new Person;
//	Person* p2 = new Student;
//	
//	delete p1;
//	delete p2;
//
//	return 0;
//}


//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//int main()
//{
//    string s;
//    getline(cin, s);
//
//    int k = 0;//参数个数
//    vector<string> arr;
//
//    auto j = s.begin();
//    auto i = j;
//    for (; i != s.end(); ++i)
//    {
//        if (*i == ' ')
//        {
//            string ss(j, i);
//            arr.push_back(ss);
//            k++;
//            j = i + 1;
//        }
//        if (*i == '"')
//        {
//            i++;
//            while (*i != '"')
//            {
//                i++;
//            }
//            if (j != i - 1)
//            {
//                string ss(j + 1, i);
//                arr.push_back(ss);
//                k++;
//            }
//            j = i + 1;
//
//            //处理“”之后如果不是结尾，就要从新的定义i和j的位置！！！！
//            if (j != s.end())
//                j++, i = j;
//
//        }
//    }
//
//    //判断最后一次是否是以“”结尾的，如果不是就需要再将最后一个字符串push到arr中去
//    if (j != s.end())
//    {
//        string ss(j, i);
//        arr.push_back(ss);
//        k++;
//    }
//
//    cout << k << endl;
//    for (auto x : arr)
//    {
//        cout << x << endl;
//    }
//
//    return 0;
//}



//友元函数不具有传递性
//class B;
//class A
//{
//	friend class B;
//	friend void fun(A a, B b);
//
//	void fun1() {}
//
//	int _a = 0;
//};
//class B
//{
//	//friend void fun(A a, B b);
//	void fun2() {}
//
//	int _b = 0;
//};
//
//void fun(A a, B b)
//{
//	cout << "aaaa" << endl;
//	a.fun1();
//	b.fun2();
//	cout << "aaaa" << endl;
//}
//
//int main()
//{
//	A a;
//	B b;
//	fun(a, b);
//
//	return 0;
//}

//class B
//{
//public:
//    B()
//    {
//        cout << "def" << endl;
//    }
//    ~B()
//    {
//        cout << "de" << endl;
//    }
//
//    B(int i)
//        :data(i)
//    {
//        cout << "con" << endl;
//    }
//
//private:
//    int data;
//};
//
//B play(B b)
//{
//    return b;
//}
//
//int main()
//{
//    B temp = play(5);
//
//    return 0;
//}

//#include<iostream>
//using namespace std;
//class MyClass {
//public:
//    MyClass(int i = 0) { cout << 1; }
//
//    MyClass(const MyClass& x) { cout << 2; }
//
//    MyClass & operator=(const MyClass & x) { cout << 3; return*this; }
//
//    ~MyClass() { cout << 4; }
//};
//
//int main() {
//    MyClass obj1(1), obj2(2), obj3(obj1);
//    //1 1 2 4 4 4
//    return 0;
//}

//class A
//{
//public:
//    static int _p;
//private:
//    int _a;
//    //static int _x = 0;//不加const修饰的静态成员变量就不能在类内初始化，必须在类外初始化
//    static int _x;
//    const static int _y = 0;//加const 修饰的就可以了
//    static int const _o = 0;
//};
//int A::_x = 1;
//int A::_p = 2;

//class A
//{
////public:
//private:
//    ~A()
//    {}
//};
//int main()
//{
//    //A a;
//    //a._p;//静态成员任然受访问限定符的影响
//    ////既可以通过对象来调用，也可以是直接指明类作用域来访问
//    //cout << A::_p << endl;
//
//    //A a;
//    A* P = new A;//析构函数设置为私有的就不能直接创建A对象了
//    //而必须通过new
//
//    return 0;
//}

class AA
{
public:
    void fun1()
    {
        cout << "A" << endl;
    }
};

class BB : public AA
{
public:
    void fun1(int)//隐藏
    {
        cout << "B" << endl;
    }
};

//class A 
//{ 
//public: 
//    void test(float a) { cout << a; } 
//}; 
//class B :public A 
//{ 
//public: 
//    void test(int b) { cout << b; }//形成隐藏
//}; 
//void main() 
//{   A* a = new A;
//    B* b = new B;
//    a = b;//切片
//    a->test(1.1);//1
//} 
//int main()
//{
//    BB b;
//    AA a = b;//发生的是切片，将子类的父类部分赋值给a，那么a在调用构成隐藏的成员函数时就还是调用的父类的
//    a.fun1();
//    b.fun1(0);
//
//    return 0;
//}

//class A 
//{
//public:
//    virtual void fun()=0 {
//        cout << "xu" << endl;
//    }
//};
//抽象类不能实例化对象
//不能作为函数的参数和返回值
//但是定义抽象类指针
//class A
//{
//public:
//    virtual void fun() {
//    }
//};
//
//class B 
//{
//public:
//    virtual void fun(){
//    }
//};
//
//class C : public A, public B
//{
//public:
//    virtual void fun() {
//    }
//
//    virtual void fun11() {
//    }
//};
//int main()
//{
//    //A a;
//    //A* p;
//    A a;
//    A a1;
//    A a2;//一个类的不同对象共用一个虚表
//
//    B b;
//    C c;//c当中有两个虚表，其中将fun11放在了第一张虚表当中，通过内存窗口便能看到
//
//    return 0;
//}


//class A
//{
//public:
//    virtual void fun(){}
//};
//class B : public A
//{
//public:
//    virtual void fun(){}
//};
//int main()
//{
//    A a;
//    //A a1;
//    B b;
//    return 0;
//}

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int main()
//{
//    int sum = 0, amass = 1;
//    int n;
//    cin >> n;
//    vector<int> arr;
//    arr.resize(n);
//    for (auto& e : arr) {
//        cin >> e;
//        sum += e;//求和
//        amass *= e;//求积
//    }
//
//    int count = 0;//计数
//    if (sum > amass)
//        count++;
//    sum = 0, amass = 1;
//
//    //先排序
//    sort(arr.begin(), arr.end());
//    for (int j = arr.size() - 2; j >= 0; --j)
//    {
//        for (int i = j; i >= 0; --i)
//        {
//            sum += arr[i];
//            amass *= arr[i];
//        }
//        if (sum > amass)
//            count++;
//        sum = 0, amass = 1;
//    }
//
//    cout << count << endl;
//    return 0;
//}

//struct A
//{
//    void foo() { cout << "foo"; }
//    virtual void bar() { cout << "bar"; }
//    A() { bar(); }
//};
//
//struct B : A
//{
//    void foo() { cout << "b_foo"; }
//    void bar() { cout << "b_bar"; }//虚函数的重写
//};
//
//int main()
//{
//    A* p = new B;
//    p->foo();
//    p->bar();
//
//    delete p;
//    return 0;
//}

//class A
//{
//public:
//    void f() { cout << "A" << endl; }
//    //virtual ~A(){}
//};
//
//class B : public A
//{
//public:
//    virtual void f() { cout << "B" << endl; }
//    virtual void f1() { cout << "B" << endl; }
//
//    //virtual ~B() {}
//};

// 用程序打印虚表
typedef void(*VF_PTR)();

//void PrintVFTable(VF_PTR table[])
void PrintVFTable(VF_PTR* table)
{
	for (int i = 0; table[i] != nullptr; ++i)
	{
		printf("[%d]:%p->", i, table[i]);
		/*VF_PTR f = table[i];
		f();*/
	}
	cout << endl;
}
//int main()
//{
//    A a;
//    B b;
//    //PrintVFTable((VF_PTR*)(*(int*)&a));
//    PrintVFTable((VF_PTR*)(*(int*)&b));
//
//    /*A* a = new B;
//    a->f();
//    delete a;*/
//    return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//    vector<vector<int>> vv;
//    int n;
//    cin >> n;
//    vv.resize(n);
//    for (int i = 0; i < n; ++i) {
//        vv[i].resize(2 * n + 1, 0);
//    }
//
//    for (int i = 0; i < n; ++i)
//    {
//        int j = 0;
//        int m = n - i - 1;
//        while (m--) {
//            j++;
//        }
//
//        int h = 2 * i + 1;
//        while (h--)
//        {
//            if (i == 0 || i == 1 || j == 0)
//                vv[i][j] = 1;
//            else
//                vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j] + vv[i - 1][j + 1];
//            j++;
//        }
//    }
//
//    bool ret = false;
//    for (int i = 0; i < vv[n - 1].size(); ++i)
//    {
//        if (vv[n - 1][i] % 2 == 0 && vv[n - 1][i] != 0)
//        {
//            ret = true;
//            cout << i + 1;
//            break;
//        }
//    }
//
//    if (!ret)
//        cout << -1;
//    return 0;
//}

//#include <iostream>
//#include <string>
//using namespace std;
//
//bool fun_string(const string& s1, const string& s2)
//{
//    //如果没有通配符的话就直接返回false
//    bool flag = true;
//    for (auto& p : s1)
//    {
//        if (p == '*' || p == '?')
//        {
//            flag = false;
//            break;
//        }
//    }
//    if (flag)
//        return false;
//
//    //如果第一个通配字符出现的字符串不一样，就返回false
//    int i = 0;
//    while (s1[i] != '*' && s1[i] != '?')
//    {
//        if (s1[i] != s2[i])
//            return false;
//        i++;
//    }
//
//    int j = i;
//    string ss;
//    //i来到了第一个匹配字符的位置
//    for (; i < s1.size(); ++i)
//    {
//        int step = 0;
//        while (s1[i] == '*' || s1[i] == '?')
//        {
//            ss.push_back(s1[i++]);
//        }
//
//        if (!ss.empty())
//        {
//            int range = false;
//            for (auto& s : ss)
//            {
//                if (s == '?')
//                    step += 1;
//                else if (s == '*')
//                {
//                    range = true;// 可以走>=step
//                }
//            }
//
//            //再来走匹配字符
//            if (range == false)
//            {
//                //只能走step步
//                while (step--)
//                {
//                    j++;
//                }
//            }
//            else {
//                while (step--)
//                {
//                    j++;
//                }
//                while (s2[j] != s1[i] && j < s2.size())
//                {
//                    j++;
//                }
//                if (j == s2.size())
//                    return false;
//            }
//        }
//        else
//            continue;
//
//        if (s1[i] != s2[j] && i < s1.size())
//            return false;
//        ss.clear();
//    }
//    return true;
//}
//
//int main()
//{
//    string s1;
//    string s2;
//
//    getline(cin, s1);
//    getline(cin, s2);
//
//    //将两个字符串的字母全部转化为小写
//    for (auto& s : s1)
//    {
//        if (s >= 'A' && s <= 'Z')
//            s += 32;
//    }
//    for (auto& s : s2)
//    {
//        if (s >= 'A' && s <= 'Z')
//            s += 32;
//    }
//
//    bool ret = fun_string(s1, s2);
//    if (ret)
//    {
//        cout << "true" << endl;
//    }
//    else
//    {
//        cout << "false" << endl;
//    }
//
//    return 0;
//}

//class A
//{
//public:
//    void foo()
//    {
//        printf("1");
//    }
//    virtual void fun()
//    {
//        printf("2");
//    }
//};
//class B : public A
//{
//public:
//    void foo()
//    {
//        printf("3");
//    }
//    void fun()
//    {
//        printf("4");
//    }
//};
//int main(void)
//{
//    A a;
//    B b;
//    A* p = &a;
//    p->foo();//1
//    p->fun();//2
//    p = &b;
//    p->foo();//1
//    p->fun();//4
//    A* ptr = (A*)&b;//强步强转都一样的
//    ptr->foo();//1
//    ptr->fun();//4
//    return 0;
//}

//class A
//{
//public:
//    void f()
//    {
//        printf("A\n");
//    }
//};
//class B : public A
//{
//public:
//    virtual void f()
//    {
//        printf("B\n");
//    }
//};
//int main()
//{
//    A* a = new B;
//    a->f();//不够成多态,父类指针去调用，调用的就是父类的成员函数
//    delete a;
//    return 0;
//}

#include <vector>
class Gloves {
public:
    int findMinimum(int n, vector<int> left, vector<int> right) {
        int left_sum = 0, left_min = INT_MAX;
        int right_sum = 0, right_min = INT_MAX;

        int sum = 0;
        for (int i = 0; i < n; ++i)
        {
            if (left[i] == 0 || right[i] == 0)
            {
                sum += left[i] + right[i];
            }
            else
            {
                left_sum += left[i];
                right_sum += right[i];
                left_min = min(left_min, left[i]);
                right_min = min(right_min, right[i]);
            }
        }
        sum += min(left_sum - left_min + 1, right_sum - right_min + 1) + 1;
        return sum;
    }
};
//int main()
//{
//    vector<int> a1;
//    vector<int> a2;
//    a1.push_back(0);
//    a1.push_back(7);
//    a1.push_back(1);
//    a1.push_back(6);
//
//    a2.push_back(1);
//    a2.push_back(5);
//    a2.push_back(0);
//    a2.push_back(6);
//
//    Gloves g;
//    g.findMinimum(4, a1, a2);
//
//    return 0;
//}

//int main()
//{
//    int a = 10;
//    double f = 2*10.2;
//
//    if (a > f) cout << "cerr" << endl;
//    else if (a < f) cout << "yes" << endl;
//    else cout << "no" << endl;
//    return 0;
//}


using namespace std;

struct list_node {
    int val;
    struct list_node* next;
};

list_node* input_list(void)
{
    int n, val;
    list_node* phead = new list_node();
    list_node* cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node* new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node* reverse_list(list_node* head, int L, int R)
{
    //////在下面完成代码
    //先找到要翻转的区间
    list_node* cur = head;
    list_node* prev = head;
    while (--R)
    {
        cur = cur->next;
    }
    while (--L)
    {
        prev = prev->next;
    }
    //cout << prev->val << " " << cur->val << endl;

    //开始翻转
    for (int i = L; i < R; ++i)
    {
        //翻转的本质还是头插操作
        list_node* _next = cur->next;
        list_node* prev_next = prev->next;

        cur->next = prev;
        prev->next = _next;

        prev = prev_next;
    }
    return cur;
}

void print_list(list_node* head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

//
//int main()
//{
//    int L, R;
//    list_node* head = input_list();
//    scanf("%d%d", &L, &R);
//    list_node* new_head = reverse_list(head, L, R);
//    print_list(new_head);
//    return 0;
//}


// write your code here cpp

//#include <string>
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//int main()
//{
//    string str;
//    char ch[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K','L','M', 'N', 'O', 'P', 'Q'
//                 , 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
//    while (getline(cin, str))
//    {
//        for (auto& c : str)
//        {
//            if (c == ' ') cout << " ";
//            else
//            {
//                //字母
//                cout << ch[(c - 'A' + 21) % 26];
//            }
//        }
//        cout << endl;
//    }
//    return 0;
//}

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int main()
//{
//    int n = 0;
//    vector<int> arr;
//    while (cin >> n)
//    {
//        for (int i = 2; i <= n / 2; ++i)
//        {
//            if (n % i == 0)
//            {
//                arr.push_back(i);
//                n /= i;
//                i = 1;
//            }
//        }
//        //去重
//        unique(arr.begin(), arr.end());
//        cout << arr.size() << endl;
//        arr.clear();
//    }
//    return 0;
//}

//#include <thread>
//int main()
//{
//    thread t1([](int num) {
//            //打印奇数
//        for (int i = 1; i <= 100; i++)
//        {
//            if (i % 2 != 0)
//                cout << "线程" << num << " : " << i << endl;
//            this_thread::sleep_for(chrono::milliseconds(100));
//        }
//        }, 1);
//
//    thread t2([](int num) {
//        //打印偶数
//        for (int i = 1; i <= 100; ++i)
//        {
//            if (i % 2 == 0)
//                cout << "线程" << num << " : " << i << endl;
//            this_thread::sleep_for(chrono::milliseconds(100));
//        }
//        }, 2);
//
//    t1.join();
//    t2.join();
//
//    return 0;
//}

